package 华为OD机试真题2023.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HJ30_云短信平台优惠活动 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/30.txt"));
        MyUtil.START();
        Solution(in);
        MyUtil.END();
    }

    static int max = 0;
    static int tmp = 0;

    static void Solution(Scanner in) {
        int N = in.nextInt();
        in.nextLine(); // 吸收回车
        String[] sArray = in.nextLine().split(" ");
        int[] nums = new int[sArray.length];
        for (int i = 0; i < sArray.length; i++) {
            nums[i] = Integer.parseInt(sArray[i]);
        }
        dfs(nums, 0, N);
        System.out.println(max);
    }

    static void dfs(int[] nums, int startIndex, int target) {
        if (target < 0) {
            return;
        }
        if (startIndex == nums.length) {
            max = Math.max(max, tmp);
            return;
        }
        int now = nums[startIndex];
        int price = startIndex + 1;
        tmp += now;
        dfs(nums, startIndex + 1, target - price);
        tmp -= now;
        dfs(nums, startIndex + 1, target);
    }
}
